package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 中档题
 * 82. 删除排序链表中的重复元素 II
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 *
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 *
 * 输入：head = [1,1,1,2,3]
 * 输出：[2,3]
 * @author zjj_admin
 * @date 2022/11/3 15:24
 */
public class DeleteDuplicateItem2 {

    public static void main(String[] args) {

    }


    /**
     * 思路
     *
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 40.8 MB
     * 击败
     * 76.79%
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode curr = head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        boolean flag = false;
        while (curr != null){
            //当存在相同的数据时，指出最后一个相同的数据
            while (curr.next != null && curr.val == curr.next.val){
                curr = curr.next;
                flag = true;
            }
            if(flag){
                pre.next = curr.next;
                flag = false;
            }else {
                pre = curr;
            }
            curr = curr.next;
        }
        return dummy.next;
    }

}
